Corelab Seminar
2020-2021
Angeliki Giannou
The stochastic asymptotic stability of discrete FTRL dynamics
Abstract.
This talk examines the asymptotic stability of all Nash equilibria under the general scheme of discrete FTRL dynamics in the presence of noise. More specifically, if we consider the class of finite games in normal form, under continuous FTRL dynamics, [FVGLMP20] states that a Nash equilibrium is asymptotically stable if and only if it is a strict Nash equilibrium. A pertinent question that instantly arises is: What happens in the case of discrete FTRL dynamics? Going one step further we study the asymptotic stability of all Nash equilibria under discrete FTRL dynamics in two eminent cases. The first one is the bandit case and the second is a more general noisy version of FTRL. Our theorems state that in both cases, a Nash equilibrium is asymptotically stable if and only if it is a strict Nash equilibrium.
[FVGLMP20]: No-regret learning and mixed nash equilibria: they do not mix (NeurIPS 2020)